package com.jia.leetCode;

import com.jia.jianzhiOffer.TreeNode;

/**
 * 
 * @author Jia
 * 
 */
public class Pro0002 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        int val1 = 0, val2 = 0;
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        while(l1!=null || l2!=null) {
            val1 = (l1!=null)? l1.val : 0;
            val2 = (l2!=null)? l2.val : 0;
            curr.next = new ListNode((val1 + val2 + carry) % 10);
            carry = (val1 + val2 + carry)/10;
            curr = curr.next;
            if(l1!=null)
                l1 = l1.next;
            if(l2!=null)
                l2 = l2.next;
            if(l1 == null && l2 == null && carry!=0) {
                curr.next = new ListNode(1);
            }
        }
        return dummy.next;
    }

	/**
	 * Definition for singly-linked list. public class ListNode { int val;
	 * ListNode next; ListNode(int x) { val = x; } }
	 */
	public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        ListNode l3 = null;
        ListNode p,q;
        int value = 0; 
        int addValue = 0;
        p = l1;
        q = l2;
        while(p!=null && q!= null) {
            value = p.val + q.val + addValue;
            addValue = value / 10;
            value %= 10;
            ListNode node  = new ListNode(value);
            node.next = l3;
            l3 = node;
            p = p.next;
            q = q.next;
        }
        while(p != null) {
            value = p.val + addValue;
            addValue = value / 10;
            value %= 10;
            ListNode node  = new ListNode(value);
            node.next = l3;
            l3 = node;
            p = p.next;
        }
        while(q!= null) {
            value = q.val + addValue;
            addValue = value / 10;
            value %= 10;
            ListNode node = new ListNode(value);
            node.next = l3;
            l3 = node;
            q = q.next;
        }
        if(addValue != 0) {
            ListNode node = new ListNode(addValue);
            node.next = l3;
            l3 = node;
        }
        p = null;
        q = l3;
        while(q!= null) {
            l3 = q;
            q = q.next;
            l3.next = p;
            p = l3;
        }
        return l3;
    }
	class ListNode {
		int val;
		ListNode next;
		public ListNode(int x) {val = x;}
	}

    public static class Pro0302 {
        public static class Peo0236 {
            /**

            二叉树最近公共祖先
            三种情况：
            1.p q 一个在左子树 一个在右子树 那么当前节点即是最近公共祖先
            2.p q都在右子树
            3.p q 都在左子树
            **/
            public com.jia.jianzhiOffer.TreeNode lowestCommonAncestor(com.jia.jianzhiOffer.TreeNode root, com.jia.jianzhiOffer.TreeNode p, com.jia.jianzhiOffer.TreeNode q) {
                if(root == null) return null;
                if(root == p || root == q)
                    return root;
                com.jia.jianzhiOffer.TreeNode left = lowestCommonAncestor(root.left, p, q);
                TreeNode right = lowestCommonAncestor(root.right, p, q);
                if(left != null && right != null) {
                    return root;
                }
                if(left!=null) {
                    //p q都在左子树
                    return left;
                }
                if(right != null) {
                    //p q都在右子树
                    return right;
                }
                return null;
            }
        }

        /**
         * 369. 给单链表加一
         *
         *
         * 用一个 非空 单链表来表示一个非负整数，然后将这个整数加一。

        你可以假设这个整数除了 0 本身，没有任何前导的 0。

        这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。

        示例:

        输入: [1,2,3]
        输出: [1,2,4]

        来源：力扣（LeetCode）
        链接：https://leetcode-cn.com/problems/plus-one-linked-list
        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         *
         *
         * @author Administrator
         *
         */
        public static class Por0369 {
            int carry = 1;
            public com.jia.leetCode.ListNode plusOne(com.jia.leetCode.ListNode head) {
                com.jia.leetCode.ListNode node = help(head);

                if(carry == 1) {
                    com.jia.leetCode.ListNode listNode = new com.jia.leetCode.ListNode(1);
                    listNode.next = node;
                    return listNode;
                }

                return node;
            }
            private com.jia.leetCode.ListNode help(com.jia.leetCode.ListNode head) {
                if(head == null) return null;
                if(head!=null) {
                    com.jia.leetCode.ListNode node = plusOne(head.next);
                    int temp = carry + head.val;
                    head.val = temp % 10;
                    carry = temp / 10;
                }
                return head;
            }
        }
    }
}
